perm filename STRUCT.DOC[SYS,HE]1 blob
sn#046694 filedate 1973-06-06 generic text, type T, neo UTF8
COMMENT ⊗ VALID 00014 PAGES
RECORD PAGE DESCRIPTION
00001 00001
00005 00002 DISPLAY ROUTINES
00008 00003 SAVE/RESTORE MECHANISM
00009 00004 PROTOTYPE DATA STRUCTURES - variables,lines and body structure
00013 00005 PROTOTYPES CONT. - feature structure
00016 00006 PROTOTYPES CONT. - more feature structure
00018 00007 EDGE DATA STRUCTURE
00022 00008 LINE DATA STRUCTURE
00026 00009 VERTEX DATA STRUCTURE
00030 00010 PATH AND SCENE FEATURE DATA STRUCTURES
00032 00011 XREF TABLES
00033 00012 MAPTRC WORD
00036 00013 LFDIF AND MODIF FORMATS
00038 00014 PARSER
00042 ENDMK
⊗;
DISPLAY ROUTINES
Only active portions of data structure are displayed.
All POGs are stored in one buffer, in order. The first word
for each POG is size/brightness word if POG is active and to be displayed;
it is a jump to the start of the next POG if inactive or already displayed.
DADR[I] is the index into the buffer for the start of the Ith POG.
DBRSI[I] is the size/brightness word for POG to store when POG becomes
active
DICH[I] is true if POG must be regenerated I=0 refers to all POGs
DION[I] is true if POG is being displayed.e displayed.
DISP[I] is true if POG is to be displayed.
DISFUS is index of first word of user generated display in buffer
DISLAS is number of user generated words in buffer
DFORCE true forces necessary updating (overrides NODIS and DHOLD)
DHOLD true suppresses display updating (user controlled)
NODIS true suppresses display updating (program controlled). Used
during data structure expansion.
POG WHAT WHERE
1 frame 4 to 13
2 edge pairs 14 to y←55+NOEPL+NOEPL%10
3 edge marks y+1 to j←y+210
4 lines j+1 to k←j+MAXNOV+5
5 line marks k+1 to l←k+MAXNOV+5
6 vertices l+1 to m←l+2*MAXNOV+5
7 m+1 end of used portion of buffer (DADR only)
Edge pairs are displayed as points if IAEDG≠2, else as line segments.
Vertices are displayed for line ends if CVLIN
DRX, DRY is center of display rectangle
IRX, IRY is center of internal coordinate rectangle
DSCX, DSCY are scale factors for display coordinates
ISCX, ISCY are inverse of DSCX, DSCY
If windowing (WIND true) edge points and strings are displayed if
-510≤x≤510 and (-510 max LOCT+5)≤y≤510, where LOCT is top of page printer.
Lines are displayed if ?????.
SAVE/RESTORE MECHANISM
file extensions set to .TEM during initialization and whenever
the data structure for the extension is altered. Automatic
saves are skipped when extension is not .TEM.
Automatic restores delete file if extension is .TEM.
If extension is .TEM, automatic saves use files
EDSAVE.TEM for edges
LISAVE.TEM for lines
PRSAVE.TEM for prototypes
For edge data input extensions are:
.DAT Hueckel format
.EDG Pingle format
.SED sorted file (transform and RDEP only entered)
.TEM temporary save file
PROTOTYPE DATA STRUCTURES - variables,lines and body structure
MXNPRO 5 maximum number of prototypes
MAXPLT 12*MXNPRO maximum number of prototype lines
MAXPFT 4*MAXPLT maximum number of prototype features
NPRO number of prototypes (free storage at NPRO+1)
PVERT number of vertices
PPTRL points to start of the prototype in PLINE AND PLINEF
PLTOT total number of prototype lines (free storage at
PLTOT+1)
PFTOT total number of prototype features stored (free
storage at PFTOT+1) =PLFTOT+PCFTOT
MAXPLS maximum number of lines/prototype
MAXPVS maximum number of vertices/prototype
PLFTOT total number of line features
PCFTOT total number of compound features
PFFREE feature to prototype free storage pointer
PFREE prototype c.f. pairs free storage pointer
indexed by prototype number
STRING PNAME[1:MXNPRO] prototype name
INT. PLINES[1:MXNPRO] number of lines for each prototype
INT. PVERTS[1:MXNPRO] number of vertices for each prototype
INT. PPTRL[1:MXNPRO] for each prototype, the index of the first word in
prototype line arrays which refer to this prototype
for each line of prototype. If line I is in prototype J, the index
is PPTR[J]+LEDG1[I]. Data for prototype I starts at PPTRL[I] and
extends for PLINES[I] entries.
INT. PLINE[1:MAXPLT] line data structure - cross reference
0-5 6B end vertex 1 (unique number
for each seperate vertex)
6-11 6B end vertex 2
12-17 6B ptr into these tables to next
line at end 1
18-23 6B ptr to next line at end 2
24 1B side 1 border?
25 1B side 2 border?
26-30 5B equivalence class
31-35 5B parallelity class (0 for all
lines || to no other)
INT. PLINE2[1:MAXPLT] 0-25 26B not used
26 1B on iff this line in the longer
(of 2) length classes for this
line's parallelity class.
27-35 9B l.f. ID.
INT. PLINEF[1:MAXPLT] line features. Bit 35 on iff l.f. non-directional
Also found in PFLST
PROTOTYPES CONT. - feature structure
indexed by feature I.D.
INTEGER PFLST[1:MAXPFT] is an ordered array of all different features for
all prototypes. L.Fs are stored first, followed by
C.F.s. Each type is ordered by magnitude.
line feature storage. One half word for the line
feature traversing the line in each direction.
Ordered with the smallest l.f. on the left.
0 1B 0
1-4 4B # of lines >180 degrees
5 1B any of the above ~ = 180 degrees?
6-9 4B # of lines < 180 degrees
10 1B any of the above ~ = 180 degrees?
11-12 2B outside angle (smallest angle from
line on the >180 side to the ≤180
side. Bits codes as:
0 <180
1 ≤180
2 >180
3 ≥180
13-14 2B 0 if converging on this side
1 if conv. or ||
2 if diverging on this side
3 if div. or ||
based on angle from last line at
start end for this side, to next
line at opposite end CCW ordered
as the l.f.
15-17 3B unused
compound feature storage. One half word for
each direction of the line pair. Ordered with
the smallest c.f. on the left.
0 1B 1
1-8 8B L.F. id for first line in this
direction.
9 1B direction that L.F. is traversed
going toward the junction: 0 as
ordered in L.F.; 1 otherwise.
10-13 4B position of other parent line CCW
around center vertex. 1+number of
rays in between
14-17 4B constellation of opposing end-rays
as for L.F.s
14 1 if intersect pointing out
from C.F.
15 1 if diverging on this side
16 1 if collinear
17 1 if parallel
PROTOTYPES CONT. - more feature structure
INT. PFPTR[0:MAXPFT] feature reference word
0 1B all mappings tried?
1-5 5B # of rays for this feature
6 1B unordered?
7-11 5B unused
12-23 12B points into CFEAT (c.f.s only)
start of list of instances of
this feature in scene.
24-35 12B pointer into PFPRO. Start of list
of instances of this feature in
prototypes.
INT. PFPRO[1:MAXPFT] prototype substructure.
0-11 12B prototype number
12-23 12B pointer to PFEAT - instances of
this feature in this prototype
24-35 12B pointer to next entry for this
feature in some other prototype.
0 at end of list.
INT. PFEAT[1:MAXPFT] has in each first word:
0 1B 1
1-11 11B prototype number
12-23 12B feature i.d.
24-35 12B # of items in sublist
followed by items. If c.f. :
0 1B 0
1 1B line 1 end at intersection
2-11 10B index of prototype line 1
12 1B 1
13 1B line 2 end at intersection
14-23 10B index of prototype line 2
24-35 12B next pointer.
If l.f.:
0 1B 0
1-11 11B index of prototype line
12 1B 0
13-23 11B equivalance class
24-35 12B next pointer. Last pointer is 0.
EDGE DATA STRUCTURE
NOEPM 10
NOEPA 0 number of edge pairs
NOEPL NOEPA+NOEPM
KICH read in length of camera transform
RDEP read in operator spacing/2 (length of edge pairs)
REAL ARRAY EAX[0:NOEPL] x coord of start of edge pair
REAL ARRAY EAY[0:NOEPL] y coord of start of edge pair
REAL ARRAY EBX[0:NOEPL] x coord of end of edge pair
REAL ARRAY EBY[0:NOEPL] y coord of end of edge pair
INTEGER ARRAY LE[0:NOEPL] edge pair connectivity. =1 if not linked,
=2 if linked to previous pair, =3 if linked to
next pair, =4 if linked to both pairs.
REAL ARRAY TFORM[1:15,1:3] camera transform
no edge pairs if EAX[0]=EAY[0]=0
LINE DATA STRUCTURE
MSAFA 20 absolute margin of safety (# of lines extra)
RMSAF .5 relative margin of safety
NOBAL NOEPA*RDEP/10 # of initial lines, estimate based on edges
MAXNOL NOBAL+NOBAL*RMSAF+MSAFA maximum number of lines
Arrays of length MAXNOL are ordered by line number and the index is the
I.D. of the line. The indices of the vertices of the line in the simple
vertex arrays are 2*I-1 and 2*I.
NOL number of lines
IFREEL pointer to first free line storage in LCREDE (none iff ifreel=0)
LDATE current level for activation-deactivation.
LNCRE1 lowest active level
LNCRE2 highest active level
REAL CXL[1:MAXNOL] line equation X*CX+Y*CY+CC=0
REAL CYL[1:MAXNOL] line equation
REAL CCL[1:MAXNOL] line equation
REAL RLEN[1:MAXNOL] line lengths
REAL ANGARG[1:MAXNOL] pos. angle ( in degrees) from pos. abscissa
REAL SQDEV[1:MAXNOL] mean square distance (0 if verified, -1 if predicted.
REAL EDGSCO[1:MAXNOL] score for edges (predicted lines)
REAL TOPSCO[1:MAXNOL] topological score (predicted lines)
INT. LEDG1[1:MAXNOL] pointer to start of edge data structure for scene
lines
INT. LEDG2[1:MAXNOL] pointer to end of edge data structure for scene
lines.
INT. LCREDE[1:MAXNOL] line creation-deletion vector. Low 12 bits are
current value. Parser uses as 3-number stack by
rotating word 12 bits at a time.
N≤-1000 means free storage. If -1000-P then P is
index of next free word. LCREDE[last]=-1000
-1000<N≤0 not currently used.
N>0 means created at level N (1 is init. fit)
and line is active (if between LNCRE1 and LNCRE2).
0<N≤1000 is the scene
1001 is scene lines used in current MAPREC
1002 is inserted lines or rays in current MAPREC
1003 is replaced lines or rays in current MAPREC
1004 is inserted lines or rays for best mapping
so far with current key (MAP)
1005 is inserted lines or rays for best total
mapping so far (PARSE)
1006 is display
1007 is unused scene lines at mapped vertices
2000+CURMAP complete objects or best partials
3000+CURMAP removed lines (replaced by insertions)
of complete objects or best partials
≥4000 is free so far (12 bits only)
VERTEX DATA STRUCTURE
MAXNOV 2*MAXNOL maximum number of composite and single verticies
MAXSCF 2*MAXNOV maximum number of compound features.
for composite vertices
NOV number of composite vertices
IFREEV pointer to first free vertex storage (none iff ifreel=0)
REAL XVCOR[1:MAXNOV] x coordinate of composite vertex. Indexed by c.v. #
REAL YVCOR[1:MAXNOV] y coordinate of vertex
INT. LVERSI[1:MAXNOV] points to one of its single vertices.
(<0 if free storage). If -1000-p then p is index
of next free word and LVERSI[last]=-1000. Indexed
like XVCOR and YVCOR.
for single vertices
The array index is the vertex number. For vertex I, the index in the arrays
of the line data structure for its line is (I+1) DIV 2.
REAL XLCOR[1:MAXNOV] x coordinates of vertices of line
REAL YLCOR[1:MAXNOV] y coordinates of vertices of line
INT. LVER[1:MAXNOV] points to next s.v. around c.v. ccw. Inactive
lines may still point to c.v.s so LCREDE must
be checked. LVER[y]=y iff free line-end
(SVANG is then =360.) N>0 iff
vertex is permanentεc.v and next linked to s.v.is
# N. N<0 iff vertex is temporaryεc.v. and next
linked to s.v. is #-N. This is true also for
inactive lines.
INT. LVERCO[1:MAXNOV] Pointers from all members of a composite vertex to
that vertex (0 for dead cv's-vertex is free).
For s.v. n, coordinates of its cv are in
XVCOR[LVERCO[n]] and YVCOR[LVERCO[n]].
INT. LTJOIN[1:MAXNOV] possible T joint at this vertex. 0 iff none (i.e. no
stopping line) N<0 iff line N is a stopping line.
N>0 iff temporary T-jointed with line (-N).
Established T joints in effect split the stopping
line, creating a new c.v.
REAL SVANG[1:MAXNOV] angles at vertices to next line in list.
INT. LAUX[1:MAXNOV] auxiliary vector
INTEGER LINK[1:MAXNOV] points to nearest vertex of the line collinear
to the line of this vertex. 0 if none.
If there are intervening lines, the links
are negative. Links are formed on the basis of
objects.
PATH AND SCENE FEATURE DATA STRUCTURES
for paths: NOT USED
INT. LPATH[1:MAXNOV]
INT. LPAOBJ[1:MAXNOV%8+5]
scene feature data structure:
SCF number of c.f.s in scene
INT.CFEAT[1:MAXSCF] 0 1B L1 end at intersection
1-11 11B i.d. of line 1
12 1B L2 end at intersection
13-23 11B i.d. of line 2
24-35 12B pointer to next CFEAT entry
for this c.f.
INT. LFEAT[1:MAXNOL] line features (index by line number). 0 if no l.f. in
central table for this line. Negative if l.f. is
ordered contrary to line.
0 1B 1 if partially similar l.f.
1 1B if B1=1: 1 if 2nd vertex ok, 1st
amended; 0 if vica versa.
2 1B same direction as prototype line?
3-35 33B i.d. of l.f.
XREF TABLES
collinear lines :
RCOL[V] distance to center of gap
lines intersect outside
RAS[V] distance to intersection from vertex v
RBS[V] distance to intersection from other vertex
IPS[V] # of closest vertex of other line, negative if collinear
lines intersect inside second of them
RK[V] distance to intersection from first vertex, V
=-1 if this line wholely inside other line
RBK[V] distance from intersection to closest vertex of other line
IPK[V] closest vertex # on other line
MAPTRC WORD
This word is read in octal and consists of flag bits for parser and
mapping routines. The original value is the argument to the parse command.
The codes are read in a as string of letters (no blanks between them) and
decoded. PI means pause and input new string. It turns on the pause bit
for the bit immediately preceding it. It is illegal for those bits not
having pause bits. RESET returns -1 and NULL returns 0.
Codes not recognized are typed and a new string is requested; the input
TTY buffer is cleared before this input.
After a pause : causes continuation of the program and ←n: causes
continuation after decoding n as new MAPTRC string
BIT CODE WORD DESCRIPTION
35 NR 1 display each new ray
34 2 pause after 35
33 OV 4 display each orbited vertex
32 10 pause after 33
31 PM 20 display each partial mapping
30 40 pause after 31
29 BM 100 display each best partial (map)
28 200 pause after 29
27 BP 400 display each best partial (parse)
26 1000 pause after 27
25 TT 2000 trace output to TTY
24 4000 pause after 25
23 TD 10000 trace output to PARSnn.TRC
22 PK 20000 pause after each new key
21 TL 40000 type trace line number
20 PD 100000 plot display
19 SK 200000 display scene for each key
18 400000 pause after 19
17 SI 1000000 display scene for each isolation
16 2000000 pause after 17
If MAPTRC=-1, the previous analysis is flushed so the parse can be redone
and MAPTRC←0. DO NOT USE.
LFDIF AND MODIF FORMATS
LFDIF: NOT USED
0 1B 1 if change (meaningful only for || case) * 1st position
1 1B 1 if deletion, 0 if insertion *
2 1B 1 if ||, 0 if div/conv *
3 1B 1 if deletion, 0 if insertion . other positions
4-7 4B number of lines to be inserted/deleted .
8-11 4B start position +according to which lines .
+of the vertex the first .
12-15 4B end position +and last positions would .
+correspond to after alter-.
+ing the special line .
16-17 2B character tags
0 no lines, no change
1 lines, no change
10 change, unambiguous
11 change, ambiguous
same for other side
MODIF:
high order 2 bits:
1 if ambiguous
1 if bare before insertion
followed by two bit positions for each ray at this vertex
00 if no change
01 if insert new ray
10 if delete present ray
11 if ambiguous
PARSER
matching template:
PARCLA[1:PLIN] parallelity class for each line of prototype
LENCAT[1:PLIN] length class for each line of prototype
LENDV[1:PLIN,0:1] for each line of prototype, the number of the
vertex at each end
LENDP[1:PLIN,0:1] for each line of prototype, the index of the
next line CCW around each vertex
recursive structure:
MAPORD[1:PLIN] the prototype lines referenced so far, in time
order.
MPORDS[1:2*PLIN] indexed by recursive level and contains pointers
to the currently referenced MAPORD entries at
each level.
MAPIS[1:2*PLIN] indexed by recursive level and contains pointers
to the last MAPORD items created at the level.
record mappings:
PLMAP[1:MAXPLS,0:1] for each prototype line end, the corresponding
scene line end (s.v.)
LLEV[1:PLIN,0:1] recursive level of corresponding mapping in PLMAP
negative for INCOV
PLMAPO[1:PLIN,0:1] 1 level PDL for PLMAP during line replacement
LLEVO[1:PLIN,0:1] 1 level PDL for LLEV during line replacement
PVMAP[1:MAXPVS] for each prototype vertex, the corresponding
scene composite vertex.
VLEV[1:PVER] recursive level of corresponding mapping in PVMAP
line fusion:
LFUSE[1:PLIN,0:1] a 6-level stack, for each prototype line,
containing pointers into LFUSES
LFUSES[1:63] backup info for fusion.
misc.:
LENARG[0:PLIN,0:1,0:1]
PARARG[0:PLIN]
RRR[0:1]
RNUM[0:1]
EVA[1:PLIN]
INSLEV[1:PLIN] recursive level of inserted line
LFTSTL[1:PLIN] recursive level where l.f. consistancy test true if≠0
to save best mappings:
PARTS[1:63,0:1+MAXPLS%3] first index is mapping number, second is scene line
numbers corresponding to prototype lines stored 3 per
word starting in word 1. -1 if no such line.
word 0 contains:
0-5 6B prototype number
6-8 3B completion code
00 complete
01 partial - no completion
11 partial - completion attempted
10 completed partial
9-35 27B score for mapping
FLMAPS[1:MAXNOV] mapping keys stored, in time order during c.f. pass
0-10 11B scene line #
11-22 12B prototype #
23-34 12B prototype line #
35 1B 1 if feature not in direction of line